A computer network is a geographically distributed collection of interconnected subnetworks for transporting data between nodes, such as computers. A local area network (LAN) is an example of such a subnetwork. The network's topology is defined by an arrangement of client nodes that communicate with one another, typically through one or more intermediate network nodes, such as a router or switch. As used herein, a client node is an endstation node that is configured to originate or terminate communications over the network. In contrast, an intermediate network node is a node that facilitates routing data between client nodes. Communications between nodes are typically effected by exchanging discrete packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
The data packets transferred among the nodes may include fixed-sized data cells and/or variable-sized data frames. Each data packet typically comprises “payload” data prepended (“encapsulated”) by at least one network header formatted in accordance with a network communication protocol. The network headers include information that enables the client nodes and intermediate nodes to efficiently route the packet through the computer network. Often, a packet's network headers include at least a data-link (layer 2) header and an internetwork (layer 3) header, as defined by the Open Systems Interconnection (OSI) Reference Model. The OSI Reference Model is generally described in more detail in Section 1.1 of the reference book entitled Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein.
The data-link header provides information for transmitting the packet over a particular physical link (i.e., a communication medium), such as a point-to-point link, Ethernet link, wireless link, optical link, etc. To that end, the data-link header may specify a pair of “source” and “destination” network interfaces that are connected by the physical link. A network interface contains the mechanical, electrical and signaling circuitry and logic used to couple a network node to one or more physical links. A network interface is often associated with a hardware-specific address, known as a media access control (MAC) address. Accordingly, the source and destination network interfaces in the data-link header are typically represented as source and destination MAC addresses. The data-link header may also store flow control, frame synchronization and error checking information used to manage data transmissions over the physical link.
The internetwork header provides information defining the packet's logical path (or “virtual circuit”) through the computer network. Notably, the path may span multiple physical links. The internetwork header may be formatted according to the Internet Protocol (IP), which specifies IP addresses of both a source and destination node at the end points of the logical path. Thus, the packet may “hop” from node to node along its logical path until it reaches the client node assigned to the destination IP address stored in the packet's internetwork header. After each hop, the source and destination MAC addresses in the packet's data-link header may be updated, as necessary. However, the source and destination IP addresses typically remain unchanged as the packet is transferred from link to link in the network.
In operation, a client node sends a data packet to a network interface of the intermediate network node. The intermediate network node determines how to process the packet, e.g., based on which network interface the packet is received. For example, the intermediate network node may perform a path switching function that simply re-directs the packet from one network interface to another. In this case, the packet may be transmitted over a network interface that has been previously associated with the packet's destination MAC address.
Alternatively, the intermediate network node may perform a path determination, or forwarding decision, function that selects the most appropriate network interface to forward the packet. Specifically, the intermediate network node may parse a destination IP address from the packet's internetwork header and perform an “address lookup” operation to locate routing information corresponding to the parsed address. Here, routing information is broadly understood to include any information, such as adjacency information, bridge-forwarding information, etc., that may be used to determine the packet's next hop, and, in some cases, provide other services such as quality-of-service, billing, and so forth. After the packet's next-hop address is identified using the located routing information, the packet's layer-2 (MAC) information may be modified before the packet transmitted to its next destination.
Typically, forwarding decisions are performed by a forwarding engine module executing in the intermediate network node. The forwarding engine, or data plane, is configured to process received data packets and render forwarding decisions based on a predetermined set of routing information. A router operating system, or control plane, often manages the set of routing information, ensuring that it remains up-to-date for the forwarding engine to access. In addition, the router operating system may provide other management services in the intermediate network node. For instance, the operating system may cooperate with other nodes in the network to disseminate and process network-topography information in accordance with a conventional network protocol, such as the Open Shortest Path First (OSPF) protocol. To that end, the operating system may be configured to process control packets addressed to the intermediate network node. The data and control planes are often implemented as separate processes (or threads) executing on a uniprocessor or multi-processor system. Those skilled in the art will appreciate that the control and data planes may be implemented in various arrangements of hardware, software, or combinations thereof.
Conventional forwarding engines often process received data packets using a directed forwarding graph. As understood in the art, the directed graph includes one or more graph nodes that are interconnected by a set of “edges.” Each edge connects a pair of graph nodes and associates a direction for progressing from one node to the other. In this sense, each edge in the directed forwarding graph is a “one-way” (i.e., unidirectional) edge. A single graph node may be coupled to one or more other graph nodes by a corresponding set of one-way edges. Thus, a path may be traversed through the forwarding graph by moving from node to node in a direction defined by the nodes' interconnecting edges.
Each graph node in the forwarding engine's directed forwarding graph is associated with a corresponding forwarding operation. That is, each graph node is associated with a corresponding set of forwarding instructions that, when executed, enable the forwarding engine to perform the node's forwarding operation. The forwarding graph may be statically created so that packets of the same type will traverse a predictable, deterministic path through the graph. As such, the forwarding engine performs the same set of forwarding operations for each packet of a given packet type. For example, a predetermined set of forwarding operations may be performed for layer-2 tunnel protocol (L2TP) packets that traverse a first path through the forwarding graph, whereas point-to-point protocol over Ethernet (PPPoE) packets follow a second forwarding-graph path and thus undergo a different set of forwarding operations. In practice, the intermediate network node usually receives data packets of the same type with few variations. Accordingly, most received data packets tend to traverse the same path in the forwarding engine's directed forwarding graph.
FIG. 1 illustrates the contents of an exemplary data packet 100 that may be received at a network interface of an intermediate network node. The packet is a conventional 802.3 Ethernet frame including, inter alia, a source MAC field 110, a destination MAC field 120, an Ethernet-type field 130, a data portion 140 and a cyclic redundancy check (CRC) field 150. Notably, the Ethernet frame may also include other data-link information (not shown), such as link-layer control (LLC) and subnetwork access protocol (SNAP) information.
The source and destination MAC address fields store, e.g., 48-bit values, that respectively identify the network interface from which the packet is sent and the network interface to which the packet is addressed. The Ethernet-type field 130 stores a value that identifies the type of data stored in the data portion 140. For example, an Ethernet-type field equal to the hexadecimal value 0x0800 may indicate that the data portion contains an IP datagram, such as an L2TP data packet. Alternatively, an Ethernet-type field equal to 0x8864 may correspond to a PPPoE protocol data unit (PDU) stored in the data portion. The CRC field 150 stores a data-integrity check value that may be used to detect and/or correct errors in the packet 100 after the packet is received by the intermediate network node.
FIG. 2 illustrates an exemplary directed forwarding graph 200 that a forwarding engine may employ for processing the data packet 100. The graph comprises a plurality of graph nodes, each associated with a different forwarding operation. For example, a first graph node 205 may be configured to retrieve (or otherwise access) the received data packet 100, e.g., stored at a known location in the intermediate network node. A second graph node 206 may examine the value of the Ethernet-type field 130 to “decode” the received packet type. Depending on the packet type, the packet 100 is directed to an appropriate subsequent graph node. For instance, IP datagrams and PPPoE PDUs may be directed to different graph nodes based on their respective Ethernet-type field values. By way of example, suppose that the packet 100 is a conventional IP version 4 (IPv4) datagram whose Ethernet-type field equals 0x0800.
In this case, the packet 100 is forwarded to a third graph node 207 that performs standard IPv4 validation operations, such as verifying that the packet's time-to-live value has not expired, validating the packet's IP-header checksums, etc. Next, the packet is directed to a fourth graph node 208 configured to route the packet to its next destination. Specifically, when the packet reaches the node 208, an IPv4 address lookup operation is performed to locate routing information identifying the packet's next hop. The packet's source and destination MAC address values 110 and 120 are then modified appropriately. Last, the updated packet 100 is passed to a fifth graph node 209 that is configured to transmit the packet over a physical link coupled to the packet's next destination.
The conventional directed forwarding graph described above suffers various disadvantages. For instance, the forwarding engine may experience a relatively large number of cache misses for each packet processed through the forwarding graph. More specifically, for each graph node that processes the packet 100, the node's corresponding set of forwarding instructions is typically loaded into an instruction cache (I-cache) memory accessible to the processing core executing the forwarding engine. In practice, the number of graph-node instructions loaded into the I-cache memory often exceeds the size, e.g., 32 kilobytes (kB), of the cache memory. Accordingly, some instructions will replace other, previously-loaded instructions. As a result, the replaced instruction(s) may not be accessible in the I-cache when the forwarding engine is ready to execute them. As understood in the art, a cache miss results when the forwarding engine attempts to retrieve information which is not resident in the cache.
Forwarding instructions that are not accessible in the I-cache, and thus result in I-cache misses, are usually retrieved from a predetermined location in a “main” instruction memory coupled to the forwarding engine's processing core. The amount of time required to retrieve instructions from the main memory is significantly longer (in terms of clock cycles) than accesses to the much faster I-cache memory. Moreover, instructions that are not located in the I-cache or in the main memory may have to be retrieved from an even slower mass storage medium in the intermediate network node. Thus, the relatively large number of I-cache misses per packet conventionally experienced by the forwarding engine may result in an excessive number of main-memory accesses and/or storage medium accesses which significantly slow the engine's forwarding operations.
In addition, the forwarding engine's performance also may be negatively affected by cache misses that occur in its data cache (D-cache) memory. One or more forwarding instructions may, when executed in the forwarding graph, instruct the processing core to retrieve data from the main memory. For instance, some of the instructions may direct the processing core to “prefetch” data into the D-cache memory before the data is accessed by subsequently loaded instruction(s). As such, the subsequent instructions can quickly access the prefetched data from the D-cache memory without having to retrieve the data from the slower main memory. Accordingly, cache misses may occur when retrieved data is written to the D-cache memory and consequently overwrites previously-retrieved data. The processing core may have to consume processing time and resources to later retrieve the over-written, “missed” data from the main memory.
Prior attempts have been made to reduce the number of I-cache and D-cache misses that occur per packet in the forwarding graph. These attempts have traditionally employed techniques for optimizing the forwarding code in the forwarding graph. Such techniques include, for example, conventional prefetch scheduling and loop-unrolling mechanisms. The effectiveness of these code-optimization techniques is based on the fact that a predictable pattern of I-cache and D-cache misses per packet can be anticipated based on knowledge of the packet's path through the forwarding graph, i.e., most received packets are of the same packet type and thus traverse the same path through the graph. In other words, packets are typically processed by predictable sequences of forwarding instructions which, in turn, result in a predictable pattern of I-cache and D-cache misses. While the prior code-optimization techniques are effective in reducing the number of I-cache and D-cache misses per packet, they generally do not reduce the number of cache misses enough to have a significant effect on the forwarding engine's performance.
It is therefore desirable to implement a forwarding engine that can further reduce the number of I-cache and D-cache misses per packet, thereby enabling the engine to process data packets faster and more efficiently through the forwarding graph.